Multilayered circuit boards require high-density drilling of small holes to provide electrical connections between strata to support an ever increasing miniaturization of electronics devices. Laser drilling machines are frequently used for drilling the holes. It is important to note some unusual aspects exist with certain laser hole drilling machines. First, there can be a minimal amount of time, called a refractory period, which must pass between laser drillings, which may cause the machine to stall at a specific hole when the hole is reached before that time has passed. Second, it is sometimes necessary for holes to be drilled multiple times. However, there is usually some period of time that must pass before the hole can be redrilled.
There are many methods for determining a sequence of holes to be drilled by a laser drilling machine, or a similar hole processing machine. A simplest method is to drill one hole, and move immediately to the next nearest hole, and continuing this sequence until all holes have been processed. However, this can become quite inefficient as the machine may require large jumps due to local minima from a poor optimization of the drilling sequence.
Another option is to formulate the problem as a traveling salesman problem (TSP). However, given the usual size of the pattern to be drilled, this would require either a very simple procedure—resulting in a poor sequence—or very long computation times.
JP 2001195112 describes a laser drilling route determination method capable of shortening the calculation time required for the determination of a route using a TSP formulation. A route for regulating the sequence of laser beam positions is determined based on information concerned with a plural of previously set drilling positions by applying the traveling salesman problem. The route determination, based on the TSP, includes a step for dividing drilling positions into a plural buckets, a step for determining a traveling route for regulating the traveling order of the plural divided buckets, a step for determining a start point of the laser beam and the end point of the laser beam in each divided bucket, and a step for determining a shortest route for laser beam positions between the start point and end point of each divided bucket and the end point of a certain bucket is connected to the start point of a bucket to be traveled next.
As shown in FIG. 2B, that method uses a predetermined serpentine ordering for the buckets, which may be suboptimal. That method also uses stalling and ending points based on a minimum distance within a next bucket, which also may be suboptimal. Finally, that method does not consider some of the particulars that can exist for laser drilling machines, such as refractory period of the laser.
Another patented method (U.S. Pat. No. 8,362,392) describes the production of an optimized sequence by evaluating a distance between each hole in the TSP, not as a Euclidean distance on the map of holes, but as a combined distance that all axes need to move to drill a given hole.